/**
 * This class represents HAL, the Mean Traversal Machine the Player competes with.
 * 
 * @author (Dilyan GEORGIEV)
 * @author (Thomas KOBER)
 * @author (Matthew MCDONALD)
 * 
 * @version (1.0)
 */
public class HAL  
{
    // Control variable for checking if the goal has been reached
    private boolean isGoal;
    
    /**
     * Calculate a path on the given map for the given Difficulty.
     * @param map the Data Structure on which to operate.
     * @param difficulty the difficulty for which to compute a path.
     */
    public int calculatePath(SpaceTree map, Difficulty difficulty)
    {
        int score = Integer.MAX_VALUE;

        switch (difficulty) {

            case EASY:
                score = this.calculateWorstFirstPath(map);
                break;

            case MEDIUM:
                score = this.calculateDepthFirstPath(map);
                break;

            case HARD:
                score = this.calculateBestFirstPath(map);
                break;

            default:
                score = this.calculateWorstFirstPath(map);
                break;
        }
        return score;
    }

    /**
     * Calculate a Depth First Path for the given map.
     * @param map the map on which to compute a depth first path.
     */
    public int calculateDepthFirstPath(SpaceTree map)
    {
        SpaceNode<Planet> node = map.getRoot();

        int goal = 0;
        SpaceNode<Planet> reachedGoal;

        goal += this.preorder(node);
        
        this.isGoal = false;
        
        return goal;
    }

    /**
     * Calculate a preorder path for the given map.
     * @param n the root/parent node on which the search should continue.
     * @return cost until goal state is reached.
     */
    private int preorder(SpaceNode<Planet> n) 
    {
        int nodes = 0;
        if (n != null && n.getData().isGoalPlanet()) {
            this.isGoal = true;

            nodes += n.getData().getCost().getValue();
            return nodes;

        } else if (n != null) { 
    
            nodes += n.getData().getCost().getValue();
            
            if (!isGoal) {
    
                nodes += preorder(n.getLeft());
                
                if (!isGoal) {
                    while (!n.hasRight()) {

                        nodes += n.getParent().getData().getCost().getValue();
                        n = n.getParent();
                    }
                }
            } 
            if (!isGoal) {
                nodes += preorder(n.getRight());
            }
        }

        return nodes;
    }

    /**
     * Calculate a Breadth First Path for the given map.
     * @param map the map on which to compute a breadth first path.
     */
    public int calculateWorstFirstPath(SpaceTree map)
    {    
       
        SpaceNode<Planet> node = map.getRoot();

        int goal = 0;
        SpaceNode<Planet> reachedGoal;

        goal += this.worstFirst(node);
       
        this.isGoal = false;
        
        return goal;
    }

    
    /**
     * Calculates the worst case scenario when going through the tree.
     * @param map the map on which to compute the worstFIrst search.
     * @return cost collected until reached the goal node.
     */
    private int worstFirst(SpaceNode<Planet> n) {
        int nodes = 0;

        // check if goal reached
        if(n != null && !n.getData().isGoalPlanet()) {
            SpaceNode<Planet> nextNode = null;

            // Check if left and right childs exist
            if(n.getLeft() != null && n.getRight()!= null) {
                int rightCost = n.getRight().getData().getCost().getValue();
                int leftCost = n.getLeft().getData().getCost().getValue();

                // Check both childs not yet visited
                if(!n.getLeft().isAlreadyVisited() && !n.getRight().isAlreadyVisited()) {
                    if(leftCost > rightCost) { // take more expensive one
                        nextNode = n.getLeft();
                    }
                    else {
                        nextNode = n.getRight();
                    }
                }
                else if(!n.getLeft().isAlreadyVisited()) { // Check left child not yet visited
                    nextNode = n.getLeft();
                }
                else if (!n.getRight().isAlreadyVisited()) { // Check right child not yet visited
                    nextNode = n.getRight();
                }
                else { // Branch exhausted, step up to parent
                    nextNode = n.getParent();
                }
            }
            else if (n.getLeft() != null) { // Check if left child exists
                if(!n.getLeft().isAlreadyVisited()) { // Check if left child not yet visited
                    nextNode = n.getLeft();
                }
                else { // Branch exhausted, step up to parent
                    nextNode = n.getParent();
                }
            }
            else if (n.getRight() != null) { // Check if right child exists
                if (!n.getRight().isAlreadyVisited()) { // Check if right child not yet visited
                    nextNode = n.getRight();
                }
                else { // Branch exhausted, step up to parent
                    nextNode = n.getParent();
                }
            }
            else { // Branch exhausted, step up to parent
                nextNode = n.getParent();
            }
            
            n.setAlreadyVisited(true);
            nodes += n.getData().getCost().getValue();
            nodes += worstFirst(nextNode);
        
        } else if (n != null && n.getData().isGoalPlanet()) { // Add cost for reaching goal planet
            nodes += n.getData().getCost().getValue();
        }

        return nodes;
    }

    /**
     * Calculate a Best First Path for the given map.
     * @param map the map on which to compute a best first path.
     */
    public int calculateBestFirstPath(SpaceTree map)
    {
        SpaceNode<Planet> node = map.getRoot();

        int goal = 0;
        SpaceNode<Planet> reachedGoal;

        goal += this.bestFirst(node);
        
        this.isGoal = false;
       
        return goal;
    }
    
    /**
     * Selects the best node which should be followed next in the path.
     * @param n the node from which further look is taken.
     * @return amount of nodes that it goes through until it reaches the goal state.
     */
    private int bestFirst(SpaceNode<Planet> n) {
        int nodes = 0;

        // check if goal reached
        if(n != null && !n.getData().isGoalPlanet()) {
            SpaceNode<Planet> nextNode = null;

             // Check if left and right childs exist
            if(n.getLeft() != null && n.getRight()!= null) {
                int rightCost = n.getRight().getData().getCost().getValue();
                int leftCost = n.getLeft().getData().getCost().getValue();

                // Check both childs not yet visited
                if(!n.getLeft().isAlreadyVisited() && !n.getRight().isAlreadyVisited()) {
                    if(leftCost < rightCost) { // take cheaper one
                        nextNode = n.getLeft();
                    }
                    else {
                        nextNode = n.getRight();
                    }
                }
                else if(!n.getLeft().isAlreadyVisited()) { // Check if left child not yet visited
                    nextNode = n.getLeft();
                }
                else if (!n.getRight().isAlreadyVisited()) { // Check if right child not yet visited
                    nextNode = n.getRight();
                }
                else { // Branch exhausted, step up to parent
                    nextNode = n.getParent();
                }
            }
            else if(n.getLeft() != null) { // Check if left child exists
                if(!n.getLeft().isAlreadyVisited()) { // Check if left child not yet visited
                    nextNode = n.getLeft();
                }
                else { // Branch exhausted, step up to parent
                    nextNode = n.getParent();
                }
            }
            else if(n.getRight() != null) { // Check if right child exists
                if(!n.getRight().isAlreadyVisited()) { // Check if right child not yet visited
                    nextNode = n.getRight();
                }
                else { // Branch exhausted, step up to parent
                    nextNode = n.getParent();
                }
            }
            else { // Branch exhausted, step up to parent
                nextNode = n.getParent();
            }
            
            n.setAlreadyVisited(true);
            nodes += n.getData().getCost().getValue();
            nodes += bestFirst(nextNode);
        
        } else if (n != null && n.getData().isGoalPlanet()) { // Add cost for reaching goal planet
            nodes += n.getData().getCost().getValue();
        }

        return nodes;
    }
}
